home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 May: Tool Chest / Developer CD Series May 1996 (Tool Chest) (Apple Computer) (1996).iso / Tool Chest / Development Tools & Languages / Dylan Related / Marlais / Marlais 0.5.9-portable sources / list.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-15  |  12.6 KB  |  622 lines  |  [TEXT/ttxt]
  1. /*
  2.  
  3.    list.c
  4.  
  5.    This software is free software; you can redistribute it and/or
  6.    modify it under the terms of the GNU Library General Public
  7.    License as published by the Free Software Foundation; either
  8.    version 2 of the License, or (at your option) any later version.
  9.  
  10.    This software is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13.    Library General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU Library General Public
  16.    License along with this software; if not, write to the Free
  17.    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  
  19.    Original copyright notice follows:
  20.  
  21.    Copyright, 1993, Brent Benson.  All Rights Reserved.
  22.    0.4 & 0.5 Revisions Copyright 1994, Joseph N. Wilson.  All Rights Reserved.
  23.  
  24.    Permission to use, copy, and modify this software and its
  25.    documentation is hereby granted only under the following terms and
  26.    conditions.  Both the above copyright notice and this permission
  27.    notice must appear in all copies of the software, derivative works
  28.    or modified version, and both notices must appear in supporting
  29.    documentation.  Users of this software agree to the terms and
  30.    conditions set forth in this notice.
  31.  
  32.  */
  33.  
  34. #include "list.h"
  35.  
  36. #include "apply.h"
  37. #include "boolean.h"
  38. #include "collection.h"
  39. #include "error.h"
  40. #include "number.h"
  41. #include "prim.h"
  42. #include "symbol.h"
  43.  
  44. /* globals */
  45.  
  46. /* primitives */
  47.  
  48. /* local function prototypes */
  49. static Object car (Object pair);
  50. static Object cdr (Object pair);
  51. static Object first (Object pair, Object default_ob);
  52. static Object second_d (Object pair, Object default_ob);
  53. static Object third_d (Object pair, Object default_ob);
  54. static Object set_car (Object pair, Object val);
  55. static Object set_cdr (Object pair, Object val);
  56. static Object list_element (Object pair, Object index, Object default_ob);
  57. static Object list_element_setter (Object pair, Object index, Object obj);
  58. static Object list_last (Object lst, Object default_ob);
  59. Object list_sort (Object lst, Object test);
  60. Object list_sort_bang (Object lst, Object test);
  61.  
  62. static struct primitive list_prims[] =
  63. {
  64.     {"%pair", prim_2, cons},
  65.     {"%head", prim_1, car},
  66.     {"%tail", prim_1, cdr},
  67.     {"%first", prim_2, first},
  68.     {"%second", prim_2, second_d},
  69.     {"%third", prim_2, third_d},
  70.     {"%head-setter", prim_2, set_car},
  71.     {"%tail-setter", prim_2, set_cdr},
  72.     {"%list-element", prim_3, list_element},
  73.     {"%list-element-setter", prim_3, list_element_setter},
  74.     {"%list-map1", prim_2, list_map1},
  75.     {"%list-append", prim_2, append},
  76.     {"%list-member?", prim_3, member_p},
  77.     {"%list-reduce", prim_3, list_reduce},
  78.     {"%list-reduce1", prim_2, list_reduce1},
  79.     {"%list-length", prim_1, list_length_int},
  80.     {"%list-reverse!", prim_1, list_reverse_bang},
  81.     {"%list-reverse", prim_1, list_reverse},
  82.     {"%list-last", prim_2, list_last},
  83.     {"%list-sort", prim_2, list_sort},
  84.     {"%list-sort!", prim_2, list_sort_bang},
  85. };
  86.  
  87. void
  88. init_list_prims (void)
  89. {
  90.     int num;
  91.  
  92.     num = sizeof (list_prims) / sizeof (struct primitive);
  93.  
  94.     init_prims (num, list_prims);
  95. }
  96.  
  97.  
  98. /*
  99.  * Cheesy global to make make_empty_list run faster
  100.  */
  101.  
  102. static Object ___empty_list = NULL;
  103.  
  104. /*
  105.  * Creates a unique empty_list value for use in constructing lists
  106.  */
  107. void
  108. initialize_empty_list ()
  109. {
  110.  
  111. #ifndef SMALL_OBJECTS
  112.     Object obj;
  113.  
  114.     if (___empty_list == NULL) {
  115.     ___empty_list = allocate_object (sizeof (struct object));
  116.  
  117.     TYPE (___empty_list) = EmptyList;
  118.     } else {
  119.     error ("initialize_empty_list: second attempt at initialization",
  120.            NULL);
  121.     }
  122. #endif
  123. }
  124.  
  125. #ifndef SMALL_OBJECTS
  126. /*
  127.  * Returns the unique empty_list value
  128.  */
  129. Object
  130. make_empty_list (void)
  131. {
  132.     return ___empty_list;
  133. }
  134. #endif
  135.  
  136. /* This gets called with (make <pair> args)
  137.  * Added to pass conformance tests.
  138.  */
  139. Object
  140. make_pair_driver (Object args)
  141. {
  142.     return cons (false_object, false_object);    /* who knows ?? */
  143. }
  144.  
  145. /* This gets called with (make <list> args)
  146.  */
  147. Object
  148. make_list_driver (Object args)
  149. {
  150.     int size;
  151.     Object size_obj, fill_obj, res;
  152.  
  153.     size = 0;
  154.     size_obj = NULL;
  155.     fill_obj = NULL;
  156.     while (!NULLP (args)) {
  157.     if (FIRST (args) == size_keyword) {
  158.         size_obj = SECOND (args);
  159.     } else if (FIRST (args) == fill_keyword) {
  160.         fill_obj = SECOND (args);
  161.     } else {
  162.         error ("make: unsupported keyword for <list> class", FIRST (args), NULL);
  163.     }
  164.     args = CDR (CDR (args));
  165.     }
  166.     if (size_obj) {
  167.     if (!INTEGERP (size_obj)) {
  168.         error ("make: value of size: argument must be an integer", size_obj, NULL);
  169.     }
  170.     size = INTVAL (size_obj);
  171.     }
  172.     if (!fill_obj) {
  173.     fill_obj = false_object;
  174.     }
  175.     /* actually fabricate the list */
  176.     if (size == 0) {
  177.     return (make_empty_list ());
  178.     } else {
  179.     res = make_empty_list ();
  180.     while (size) {
  181.         res = cons (fill_obj, res);
  182.         size--;
  183.     }
  184.     return (res);
  185.     }
  186. }
  187.  
  188. Object
  189. cons (Object car, Object cdr)
  190. {
  191.     Object obj;
  192.  
  193.     obj = allocate_object (sizeof (struct pair));
  194.  
  195.     PAIRTYPE (obj) = Pair;
  196.     CAR (obj) = car;
  197.     CDR (obj) = cdr;
  198.     return (obj);
  199. }
  200.  
  201. static Object
  202. car (Object lst)
  203. {
  204.     return (EMPTYLISTP (lst) ? lst : CAR (lst));
  205. }
  206.  
  207. static Object
  208. cdr (Object lst)
  209. {
  210.     return (EMPTYLISTP (lst) ? lst : CDR (lst));
  211. }
  212.  
  213. static Object
  214. first (Object lst, Object default_ob)
  215. {
  216.     if (PAIRP (lst)) {
  217.     return (CAR (lst));
  218.     } else if (default_ob == default_object) {
  219.     return error ("attempt to find first of empty list", NULL);
  220.     } else {
  221.     return default_ob;
  222.     }
  223. }
  224.  
  225. Object
  226. second (Object lst)
  227. {
  228.     return SECOND (lst);
  229. }
  230.  
  231. static Object
  232. second_d (Object lst, Object default_ob)
  233. {
  234.     if (PAIRP (lst) && PAIRP (CDR (lst))) {
  235.     return (SECOND (lst));
  236.     } else if (default_ob == default_object) {
  237.     error ("list has no second element", lst, NULL);
  238.     } else {
  239.     return default_ob;
  240.     }
  241. }
  242.  
  243. Object
  244. third (Object lst)
  245. {
  246.     return THIRD (lst);
  247. }
  248.  
  249. static Object
  250. third_d (Object lst, Object default_ob)
  251. {
  252.     if (PAIRP (lst) && PAIRP (CDR (lst)) && PAIRP (CDR (CDR (lst)))) {
  253.     return (THIRD (lst));
  254.     } else if (default_ob == default_object) {
  255.     error ("list has no third element", lst, NULL);
  256.     } else {
  257.     return default_ob;
  258.     }
  259. }
  260.  
  261. Object
  262. map (Object (*fun) (Object), Object lst)
  263. {
  264.     if (EMPTYLISTP (lst)) {
  265.     return (make_empty_list ());
  266.     } else {
  267.     return (cons ((*fun) (CAR (lst)), map (fun, CDR (lst))));
  268.     }
  269. }
  270.  
  271. Object
  272. map2 (Object (*fun) (Object, Object), Object l1, Object l2)
  273. {
  274.     if (EMPTYLISTP (l1) || EMPTYLISTP (l2)) {
  275.     return (make_empty_list ());
  276.     } else {
  277.     return (cons ((*fun) (CAR (l1), CAR (l2)), map2 (fun, CDR (l1), CDR (l2))));
  278.     }
  279. }
  280.  
  281. Object
  282. list_map1 (Object fun, Object lst)
  283. {
  284.     if (EMPTYLISTP (lst)) {
  285.     return (make_empty_list ());
  286.     } else {
  287.     return (cons (apply (fun, cons (CAR (lst), make_empty_list ())),
  288.               list_map1 (fun, (CDR (lst)))));
  289.     }
  290. }
  291.  
  292. Object
  293. list_map2 (Object fun, Object l1, Object l2)
  294. {
  295.     if (EMPTYLISTP (l1) || EMPTYLISTP (l2)) {
  296.     return (make_empty_list ());
  297.     } else {
  298.     return (cons (apply (fun, listem (CAR (l1), CAR (l2),
  299.                       NULL)),
  300.               list_map2 (fun, CDR (l1), CDR (l2))));
  301.     }
  302. }
  303.  
  304. Object
  305. list_length_int (Object lst)
  306. {
  307.     int len = list_length (lst);
  308.  
  309.     if (len < 0) {
  310.     return false_object;
  311.     } else {
  312.     return make_integer (len);
  313.     }
  314. }
  315.  
  316. Object
  317. append (Object l1, Object l2)
  318. {
  319.     if (NULLP (l1)) {
  320.     return (l2);
  321.     } else {
  322.     return (cons (CAR (l1), append (CDR (l1), l2)));
  323.     }
  324. }
  325.  
  326. int
  327. member (Object obj, Object lst)
  328. {
  329.     while (PAIRP (lst)) {
  330.     if (obj == CAR (lst)) {
  331.         return 1;
  332.     }
  333.     lst = CDR (lst);
  334.     }
  335.     return 0;
  336. }
  337.  
  338. Object
  339. member_p (Object obj, Object lst, Object test)
  340. {
  341.     Object l;
  342.  
  343.     l = lst;
  344.     while (!NULLP (l)) {
  345.     if (test != false_object) {
  346.         if (apply (test, listem (obj, CAR (l), NULL)) != false_object) {
  347.         return (true_object);
  348.         }
  349.     } else {
  350.         if (id_p (obj, CAR (l), make_empty_list ()) != false_object) {
  351.         return (true_object);
  352.         }
  353.     }
  354.     l = CDR (l);
  355.     }
  356.     return (false_object);
  357. }
  358.  
  359. Object
  360. listem (Object car,...)
  361. {
  362.     Object lst, fst, el, acons, cur;
  363.     va_list args;
  364.  
  365.     fst = cur = acons = cons (car, make_empty_list ());
  366.     va_start (args, car);
  367.     el = va_arg (args, Object);
  368.  
  369.     while (el) {
  370.     acons = cons (el, make_empty_list ());
  371.     CDR (cur) = acons;
  372.     cur = acons;
  373.     el = va_arg (args, Object);
  374.     }
  375.     va_end (args);
  376.     return (fst);
  377. }
  378.  
  379. Object
  380. list_reduce (Object fun, Object init, Object lst)
  381. {
  382.     Object val, vals;
  383.  
  384.     val = init;
  385.     while (!NULLP (lst)) {
  386.     val = apply (fun, listem (val, CAR (lst), NULL));
  387.     lst = CDR (lst);
  388.     }
  389.     return (val);
  390. }
  391.  
  392. Object
  393. list_reduce1 (Object fun, Object lst)
  394. {
  395.     Object val, vals;
  396.  
  397.     val = CAR (lst);
  398.     lst = CDR (lst);
  399.     while (!NULLP (lst)) {
  400.     val = apply (fun, listem (val, CAR (lst), NULL));
  401.     lst = CDR (lst);
  402.     }
  403.     return (val);
  404. }
  405.  
  406. int
  407. list_length (Object lst)
  408. {
  409.     int len;
  410.     Object fore_list, back_list, next;
  411.  
  412.     if (EMPTYLISTP (lst)) {
  413.     return 0;
  414.     } else if (CDR (lst) == lst) {
  415.     return -1;
  416.     } else {
  417.     len = 1;
  418.     back_list = lst;
  419.     fore_list = CDR (lst);
  420.     CDR (back_list) = make_empty_list ();
  421.  
  422.     /* Reverse pointers in the list and see if we end up at the head. */
  423.     while (PAIRP (fore_list)) {
  424.         next = CDR (fore_list);
  425.         CDR (fore_list) = back_list;
  426.         back_list = fore_list;
  427.         fore_list = next;
  428.         len++;
  429.     }
  430.     if ((back_list == lst) && (PAIRP (CDR (back_list)))) {
  431.         /* We ended up at the head and had at least 2 elements,
  432.          *  thus there must be a cycle.
  433.          */
  434.         len = -1;
  435.     }
  436.     /* Reverse the pointers again to repair the list. */
  437.     while (PAIRP (back_list)) {
  438.         next = CDR (back_list);
  439.         CDR (back_list) = fore_list;
  440.         fore_list = back_list;
  441.         back_list = next;
  442.     }
  443.     return len;
  444.     }
  445. }
  446.  
  447. static Object
  448. set_car (Object pair, Object val)
  449. {
  450.     CAR (pair) = val;
  451.     return (val);
  452. }
  453.  
  454. static Object
  455. set_cdr (Object pair, Object val)
  456. {
  457.     CDR (pair) = val;
  458.     return (val);
  459. }
  460.  
  461. static Object
  462. list_element (Object pair, Object index, Object default_ob)
  463. {
  464.     int i;
  465.     Object lst;
  466.  
  467.     i = INTVAL (index);
  468.     lst = pair;
  469.     if (NULLP (lst)) {
  470.     if (default_ob == default_object) {
  471.         error ("element: no such element", index, pair, NULL);
  472.     } else {
  473.         return default_ob;
  474.     }
  475.     }
  476.     while (i) {
  477.     i--;
  478.     lst = CDR (lst);
  479.     if (NULLP (lst)) {
  480.         if (default_ob == default_object) {
  481.         error ("element: no such element", index, pair, NULL);
  482.         } else {
  483.         return default_ob;
  484.         }
  485.     }
  486.     }
  487.     return (CAR (lst));
  488. }
  489.  
  490. static Object
  491. list_element_setter (Object pair, Object index, Object obj)
  492. {
  493.     int i, el;
  494.     Object lst;
  495.  
  496.     i = 0;
  497.     el = INTVAL (index);
  498.     lst = pair;
  499.     if (NULLP (lst)) {
  500.     error ("element-setter: list is empty", NULL);
  501.     }
  502.     while (!NULLP (lst)) {
  503.     if (i == el) {
  504.         CAR (lst) = obj;
  505.         return (obj);
  506.     }
  507.     i++;
  508.     lst = CDR (lst);
  509.     }
  510.     error ("element-setter: index to large for list", pair, index, NULL);
  511. }
  512.  
  513. Object
  514. list_reverse_bang (Object lst)
  515. {
  516.     Object cur, next;
  517.  
  518.     cur = make_empty_list ();
  519.     while (!NULLP (lst)) {
  520.     next = CDR (lst);
  521.     CDR (lst) = cur;
  522.     cur = lst;
  523.     lst = next;
  524.     }
  525.     return (cur);
  526. }
  527.  
  528. Object
  529. list_reverse (Object lst)
  530. {
  531.     Object cur, last;
  532.  
  533.     last = make_empty_list ();
  534.     while (!NULLP (lst)) {
  535.     last = cons (CAR (lst), last);
  536.     lst = CDR (lst);
  537.     }
  538.     return (last);
  539. }
  540.  
  541. static Object
  542. list_last (Object lst, Object default_ob)
  543. {
  544.     Object last;
  545.  
  546.     if (NULLP (lst)) {
  547.     if (default_ob == default_object) {
  548.         error ("attempt to get last of empty list", NULL);
  549.     } else {
  550.         return default_ob;
  551.     }
  552.     }
  553.     while (!NULLP (lst)) {
  554.     last = CAR (lst);
  555.     lst = CDR (lst);
  556.     }
  557.     return (last);
  558. }
  559.  
  560. int
  561. list_equal (Object l1, Object l2)
  562. {
  563.     if (id_p (l1, l2, make_empty_list ()) != false_object) {
  564.     return (1);
  565.     }
  566.     if (PAIRP (l1) && PAIRP (l2)) {
  567.     return (list_equal (CAR (l1), CAR (l2)) &&
  568.         list_equal (CDR (l1), CDR (l2)));
  569.     } else {
  570.     return (0);
  571.     }
  572. }
  573.  
  574. Object
  575. copy_list (Object lst)
  576. {
  577.     Object result, *tmp_ptr;
  578.  
  579.     result = make_empty_list ();
  580.     tmp_ptr = &result;
  581.     for (tmp_ptr = &result;
  582.      PAIRP (lst);
  583.      tmp_ptr = &CDR (*tmp_ptr), lst = CDR (lst)) {
  584.     *tmp_ptr = cons (CAR (lst), make_empty_list ());
  585.     }
  586.     return result;
  587. }
  588.  
  589. Object
  590. add_new_at_end (Object *lst, Object elt)
  591. {
  592.     Object ret = *lst;
  593.  
  594.     while (PAIRP (*lst)) {
  595.     if (CAR (*lst) == elt) {
  596.         return ret;
  597.     }
  598.     lst = &CDR (*lst);
  599.     }
  600.     *lst = cons (elt, make_empty_list ());
  601.     return ret;
  602. }
  603.  
  604.  
  605. /* Can't use qsort in sorting as use of test function will call
  606.  * function_specializers, which applies qsort, leading to all sorts
  607.  * or horrid consequences, as Unix qsort is not multi-thread or
  608.  * hierarchically nestable (even though it could be!
  609.  */
  610.  
  611. Object
  612. list_sort (Object lst, Object test)
  613. {
  614.     /* Fill this in! */
  615. }
  616.  
  617. Object
  618. list_sort_bang (Object lst, Object test)
  619. {
  620.     /* Fill this in! */
  621. }
  622.